/**初始化双向队列 */
// TypeScript 没有内置的双端队列，我们可以使用数组来实现一个简单的双向队列。
const dequeue: number[] = [];

/**入队 */
dequeue.push(1); // 在队列末尾添加元素
dequeue.push(3); // 在队列末尾添加元素
// 由于是数组实现，所以unshift的复杂度是O(n)
dequeue.unshift(2); // 在队列开头添加元素
dequeue.unshift(4); // 在队列开头添加元素

/**访问队首元素 */
const peekFirst = dequeue[0]; // 获取队列的第一个元素
const peekLast = dequeue[dequeue.length - 1]; // 获取队列的最后一个元素

/**出队 */
const popFront: number = dequeue.shift() as number; // 移除并返回队列的第一个元素
const popBack: number = dequeue.pop() as number; // 移除并返回队列的最后一个元素

/**获取队列的长度 */
const size: number = dequeue.length;

/**判断队列是否为空 */
// const isEmpty: boolean = size === 0; // 或者使用数组的length属性来判断
const isEmpty: boolean = dequeue.length === 0;

/**双向链表节点 */
class ListNode<T> {
  prev: ListNode<T> | null; //前驱节点
  next: ListNode<T> | null; // 后继节点
  val: T; //节点值

  constructor(val: T) {
    this.val = val;
    this.next = null; // 指向下一个节点
    this.prev = null; // 指向前一个节点
  }
}
// ------------------------------------------------------------------------------------
/**基于双向链表实现双向队列 */
class LinkedListDeque<T> {
  private _head: ListNode<T> | null; // 头节点
  private _tail: ListNode<T> | null; // 尾节点
  private _size: number; // 队列长度
  constructor() {
    this._head = null;
    this._tail = null;
    this._size = 0;
  }
  /**队尾入队 */
  pushBack(val: T) {
    const node = new ListNode(val);
    if (this._size === 0) {
      this._head = node;
      this._tail = node;
    } else {
      node.prev = this._tail;
      this._tail!.next = node;
      this._tail = node;//更新尾节点
    }
    this._size++;
  }
  /**队首入队 */
  pushFront(val: T) {
    const node = new ListNode(val);
    if (this._size === 0) {
      this._head = node;
      this._tail = node;
    } else {
      node.next = this._head;
      this._head!.prev = node;
      this._head = node;//更新头节点
    }
    this._size++;
  }
  /**队尾出队操作 */
  popBack(): T | null {
    if (this._size === 0) return null;
    const node = this._tail!.val;
    if (this._size === 1) {
      this._head = null;
      this._tail = null;
    } else {
      this._tail = this._tail!.prev;//出队后，将尾节点更新为它的前驱节点
      this._tail!.next = null;
    }
    this._size--;
    return node;//返回出队的值
  }
  /**队首出队操作 */
  popFront(): T | null {
    if (this._size === 0) return null;
    const node = this._head!.val; //存储头节点的值
    // 删除头节点
    let temp = this._head!.next;
    if (temp != null) {
      temp.next = null;
      this._head!.next = null;
    }
    this._head = temp;
    this._size--;
    return node;
  }
  /**访问队尾元素 */
  peekBack(): T | null {
    return this._tail?.val ?? null;
  }
  /**访问队首元素 */
  peekFront(): T | null {
    return this._head?.val ?? null;
  }
  /**获取双向队列的长度 */
  get size(): number {
    return this._size;
  }
  /**打印双向队列 */
  print(): void {
    const arr = new Array<T>();
    let node = this._head;
    while (node) {
      arr.push(node.val);
      node = node.next;
    }
    console.log('[' + arr.join(', ') + ']');
  }
}
// ------------------------------------------------------------------------------------
/**
 * 基于数组实现双向队列
 */
class ArrayDeque<T> {
  private _arr: T[];
  private _front: number; // 队首索引
  private queSize: number; // 队列长度

  constructor(capacity: number) {
    this._arr = new Array(capacity);
    this._front = 0;
    this.queSize = 0;
  }
  /**获取队列容量 */
  get capacity(): number {
    return this._arr.length;
  }
  /**获取队列长度 */
  get size(): number {
    return this.queSize;
  }
  /**队尾入队 */
  pushBack(val: T) {
    if (this.queSize === this.capacity) {
      throw new Error('队列已满');
    }
    const backIndex = (this._front + this.queSize) % this.capacity;
    this._arr[backIndex] = val;
    this.queSize++;
  }
  /**队首入队 */
  pushFront(val: T) {
    if (this.queSize === this.capacity) {
      throw new Error('队列已满');
    }
    this._front = (this._front - 1 + this.capacity) % this.capacity;//计算环形数组索引
    this._arr[this._front] = val;
    this.queSize++;
  }
  /**队尾出队 */
  popBack(): T | null {
    if (this.size === 0) {
      throw new Error('队列为空');
    }
    const backIndex = (this._front + this.queSize - 1) % this.capacity;
    const val = this._arr[backIndex];
    this.queSize--;
    return val;
  }
  /**队首出队 */
  popFront(): T | null {
    if (this.size === 0) {
      throw new Error('队列为空');
    }
    const val = this._arr[this._front];
    this._front = (this._front + 1) % this.capacity;//队首指针向后移位
    this.queSize--;
    return val;
  }
}